package medium;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author cmqzyd0700@163.com
 * @version 1.0
 * @since 2022/3/5 19:06
 */
public class No73_矩阵置零 {
    public static void main(String[] args) {
        Solution73 solution73 = new Solution73();
        int[][] matrix = new int[][]{
                {1, 2, 3, 4},
                {5, 0, 7, 8},
                {3, 2, 1, 0}
        };
        solution73.setZeroes(matrix);
        for (int[] data : matrix) {
            for (int d : data) {
                System.out.print(d + "\t");
            }
            System.out.println();
        } 
    }
}

class Solution73 {
    public void setZeroes(int[][] matrix) {
        // 时间优化
        //定义第一行列是否含0变量
        boolean hangFlag = false; //代表行,是否含0
        boolean lieFlag = false; //代表列,是否含0
        //行含0判断
        for (int lie = 0; lie < matrix[0].length; lie++) {
            if (matrix[0][lie] == 0) {
                hangFlag = true;
                break;
            }
        }
        
        //列含0判断
        for (int hang = 0; hang < matrix.length; hang++) {
            if (matrix[hang][0] == 0) {
                lieFlag = true;
                break;
            }
        }
        
        //从(1,1)开始,遇到0则将第一行列对应位置变成0
        for (int hang = 1; hang < matrix.length; hang++) {
            for (int lie = 1; lie < matrix[0].length; lie++) {
                if (matrix[hang][lie] == 0) {
                    //则对应第一行,第一列位置替换0
                    matrix[0][lie] = 0;
                    matrix[hang][0] = 0;
                }
            }
        }
        
        //根据第一行,第一列的0,延展
        //行为基准向下延展
        for (int lie = 1; lie < matrix[0].length; lie++) {
            if (matrix[0][lie] == 0) {
                for (int hang = 1; hang < matrix.length; hang++) {
                    matrix[hang][lie] = 0;
                }
            }
        }
        
        //列为基准向右延展
        for (int hang = 1; hang < matrix.length; hang++) {
            if (matrix[hang][0] == 0) {
                for (int lie = 1; lie < matrix[0].length; lie++) {
                    matrix[hang][lie] = 0;
                }
            }
        }
        
        //最后如果第一行列为0,则全部换成0
        if (hangFlag) {
            for (int lie = 0; lie < matrix[0].length; lie++) {
                matrix[0][lie] = 0;
            }
        }
        
        //最后如果第一行列为0,则全部换成0
        if (lieFlag) {
            for (int hang = 0; hang < matrix.length; hang++) {
                matrix[hang][0] = 0;
            }
        }

        
    }
}



    //public void setZeroes(int[][] matrix) {
    //    // 不使用空间
    //    //遍历数组,遇到0,十字架展开
    //    for (int i = 0; i < matrix.length; i++) {
    //        for (int j = 0; j < matrix[0].length; j++) {
    //            if (matrix[i][j] == 0) {
    //                //十字架展开
    //                //行 0- martix[0].length
    //                for (int hang = 0; hang < matrix[0].length; hang++) {
    //                    //0不能替换,遇到上一个0替换的'标',跳过,下同
    //                    if (matrix[i][hang] != 0 && matrix[i][hang] != '标') {
    //                        matrix[i][hang] = '标';
    //                    }
    //                }
    //                
    //                //列 0- martix.length
    //                for (int lie = 0; lie < matrix.length; lie++) {
    //                    if (matrix[lie][j] != 0 && matrix[lie][j] != '标') {
    //                        matrix[lie][j] = '标';
    //                    }
    //                }
    //            }
    //        }
    //    }
    //    
    //    //将所有标记替换0即可
    //    for (int i = 0; i < matrix.length; i++) {
    //        for (int j = 0; j < matrix[0].length; j++) {
    //            if (matrix[i][j] == '标') {
    //                matrix[i][j] = 0;
    //            }
    //        }
    //    }
    //    
    //}



    //public void setZeroes(int[][] matrix) {
    //    // 空间暴力(m+n)
    //    //定义行列list
    //    List<Integer> hang0 = new ArrayList<>();
    //    List<Integer> lie0 = new ArrayList<>();
    //    //遍历获取0位置的行列值
    //    for (int i = 0; i < matrix.length; i++) {
    //        for (int j = 0; j < matrix[0].length; j++) {
    //            if (matrix[i][j] == 0) {
    //                hang0.add(i);
    //                lie0.add(j);
    //            }
    //        }
    //    }
    //    
    //    //行列有值,遍历之
    //    for (int hang : hang0) {
    //        // 固定行 matrix[hang][]
    //        for (int i = 0; i < matrix[0].length; i++) {
    //            matrix[hang][i] = 0;
    //        }
    //    }
    //    
    //    
    //    //行列有值,遍历之
    //    for (int lie : lie0) {
    //        // 固定列 matrix[][lie]
    //        for (int i = 0; i < matrix.length; i++) {
    //            matrix[i][lie] = 0;
    //        }
    //    }
    //}



    //public void setZeroes(int[][] matrix) {
    //    //暴力法
    //    //数组复制
    //    int hang = matrix.length;
    //    int lie = matrix[0].length;
    //    int[][] matrixCopy = new int[hang][lie];
    //    for (int i = 0; i < hang; i++) {
    //        for (int j = 0; j < lie; j++) {
    //            matrixCopy[i][j] = matrix[i][j];
    //        }
    //    }
    //    //复制结束,遍历获取0位置,替换即可
    //    for (int i = 0; i < matrixCopy.length; i++) {
    //        for (int j = 0; j < matrixCopy[0].length; j++) {
    //            if (matrixCopy[i][j] == 0) {
    //                setZeroes(matrix, i, j);
    //            }
    //        }
    //    }
    //}
    //
    ////将,(x,y)位置的行列换成0
    //public void setZeroes(int[][] matrix, int x, int y) {
    //    // x x 0 x x x x x  --> 8 martix[8]
    //    // x x x x x x x x 
    //    //一行换为0
    //    for (int i = 0; i < matrix[0].length; i++) {
    //        matrix[x][i] = 0;
    //    }
    //    
    //    //一列换为0
    //    for (int i = 0; i < matrix.length; i++) {
    //        matrix[i][y] = 0;
    //    }
    //}